home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1 / Nebula One.iso / Financial / Stopwatch2.3 / Source / SortList.m < prev    next >
Encoding:
Text File  |  1995-06-12  |  11.3 KB  |  507 lines
  1. /*
  2.  * A subclass of List with a built-in sorting capability. The ShellSort
  3.  * code from the example program "SortingInAction" is used here, modified
  4.  * slightly to work closely with the List object's data representation, i.e.
  5.  * the array of objects pointed to by 'dataPtr'.
  6.  *
  7.  * The user of this class must set the SortingList's delegate to an object
  8.  * which responds to the 'lessThan:(int)position1 :(int)position2' method,
  9.  * which returns YES if object1 should be deemed to be "less than" object2
  10.  * in a way that makes sense to the caller.
  11.  *
  12.  * Written by Rich Plevin, 24 Jun 92.
  13.  *
  14.  * This code may be freely used, copied and modified. The author disclaims
  15.  * any warranty of any kind, expressed or implied, as to its fitness for any
  16.  * particular use.
  17.  * 
  18.  * 8/18/92 - More general structure implemented (can set sort, comparison, and
  19.  *     value methods.  (value method returns the value for sorted key).  added
  20.  *    insertion method which inserts object in order.  added sort flag and
  21.  *    autosort feature.
  22.  *
  23.  * 8/19/92 - Added mergeList method and overrode indexOf to use binary search
  24.  *
  25.  * For legal stuff see the file COPYRIGHT
  26.  */
  27. #include "SortList.h"
  28.  
  29. #define STRIDE_FACTOR 3 // good value for stride factor is not well-understood
  30. // 3 is a fairly good choice (Sedgewick)
  31.  
  32. @implementation SortList
  33.  
  34. - _updateChain
  35. {
  36.     if (!delegate) {
  37.       compObject = self;
  38.       if ([self respondsTo:compareMethod]) {
  39.         compMethod = compareMethod;
  40.     }
  41.     else {
  42.         compMethod = @selector(compare::);
  43.     }
  44.     }
  45.     else {
  46.     if ([delegate respondsTo:compareMethod]) {
  47.         compObject = delegate;
  48.         compMethod = compareMethod;
  49.     }
  50.     else if ([delegate respondsTo:@selector(compare::)]) {
  51.         compObject = delegate;
  52.         compMethod = @selector(compare::);
  53.     }
  54.     else if ([self respondsTo:compareMethod]) {
  55.         compObject = self;
  56.         compMethod = compareMethod;
  57.     }
  58.     else {
  59.         compObject = self;
  60.         compMethod = @selector(compare::);
  61.     }
  62.     }
  63.     return self;
  64. }
  65.  
  66. - initCount:(unsigned int)numSlots
  67. {
  68.     [super initCount:numSlots];
  69.     compareMethod = @selector(compare::);
  70.     compMethod = @selector(compare::);
  71.     sortMethod = @selector(shellsort);
  72.     compObject = self;
  73.     sorted = NO;
  74.     autoSort = NO;
  75.     return self;
  76. }
  77.  
  78. - (unsigned int)indexOf:anObject
  79. /* overridden to use binary search.  assumes that object used for search and
  80.  * object in list return the same key value 
  81.  */
  82. {
  83.     int    index1 = 0, index2 = numElements - 1, mid, mark, val;
  84.     
  85.     if (anObject == nil)
  86.     return NX_NOT_IN_LIST;
  87.  
  88.     if (sorted == NO)
  89.     return [super indexOf:anObject];
  90.     
  91.     mid = (index2 + index1)/2;
  92.     
  93.     while (mid > index1) {
  94.     if (anObject == dataPtr[mid])
  95.         return mid;
  96.     if ((val = (int)[compObject perform:compMethod with:anObject
  97.              with:dataPtr[mid]]) < 0) {
  98.         index2 = mid;
  99.     }
  100.     else if (val == 0) {
  101.         mark = mid;
  102.         while (val == 0) {
  103.         if (anObject == dataPtr[mark]) {
  104.             return mark;
  105.         }
  106.         mark--;
  107.         val = (int)[compObject perform:compMethod with:anObject
  108.             with:dataPtr[mark]];
  109.         }
  110.         mark = mid + 1;
  111.         while (val == 0) {
  112.         if (anObject == dataPtr[mark]) {
  113.             return mark;
  114.         }
  115.         mark++;
  116.         val = (int)[compObject perform:compMethod with:anObject
  117.             with:dataPtr[mark]];
  118.         }
  119.         return NX_NOT_IN_LIST;
  120.     }
  121.     else {
  122.         index1 = mid;
  123.     }
  124.       mid = (index2 + index1)/2;
  125.     }
  126.     if (anObject == dataPtr[index1]) {
  127.       return index1;
  128.     }
  129.     if (anObject == dataPtr[index2]) {
  130.     return index2;
  131.     }
  132.     return NX_NOT_IN_LIST;
  133. }
  134.  
  135. - addObject:anObject
  136. {
  137.     if (anObject == nil) return nil;
  138.     [super addObject:anObject];
  139.     [self update];
  140.     return self;
  141. }
  142.  
  143. - addObjectIfAbsent:anObject
  144. {
  145.     if (anObject == nil) return nil;
  146.     [super addObjectIfAbsent:anObject];
  147.     [self update];
  148.     return self;
  149. }
  150.  
  151. - insertObject:anObject at:(unsigned int)index
  152. {
  153.     id    returnObj;
  154.     
  155.     if (returnObj = [super insertObject:anObject at:index])
  156.       [self update];
  157.     return returnObj;
  158. }
  159.  
  160. - replaceObject:anObject with:newObject
  161. {
  162.     id    returnObj;
  163.     
  164.     if (returnObj = [super replaceObject:anObject with:newObject])
  165.       [self update];
  166.     return returnObj;
  167. }
  168.  
  169. - replaceObjectAt:(unsigned int)index with:newObject;
  170. {
  171.     id    returnObj;
  172.     
  173.     if (returnObj = [super replaceObjectAt:index with:newObject])
  174.       [self update];
  175.     return returnObj;
  176. }
  177.  
  178. - update
  179. /* sorts list if autoSort is enabled, otherwise just sets the sorted flag
  180.  * to NO.
  181.  */
  182. {
  183.     if (autoSort)
  184.       [self sort];
  185.     else
  186.       sorted = NO;
  187.     return self;
  188. }
  189.  
  190. - (BOOL)isSorted
  191. {
  192.     return sorted;
  193. }
  194.  
  195. - setAutoSort:(BOOL)sortFlag
  196. {
  197.     autoSort = sortFlag;
  198.     return self;
  199. }
  200.  
  201. - (BOOL)doesAutoSort
  202. {
  203.     return autoSort;
  204. }
  205.  
  206. - setDelegate:obj
  207. {
  208.     delegate = obj;
  209.     [self _updateChain];
  210.     return self;
  211. }
  212.  
  213. - delegate
  214. {
  215.     return delegate;
  216. }
  217.  
  218. - useSortMethod:(SEL)method
  219. /* sort method can be defined in a subclass or in a delegate(??).  when -sort
  220.  * is called, the SortList first checks the delegate then itself.  If neither
  221.  * can respond, then a default(shellsort) is used.
  222.  */
  223. {
  224.     sortMethod = method;
  225.     return self;
  226. }
  227.  
  228. - (SEL)sortMethod
  229. {
  230.     return sortMethod;
  231. }
  232.  
  233. - useComparisonMethod:(SEL)method
  234. /* sets the method used to compare the objects.  Overrides SortList's and
  235.  * delegate's -compare:: methods.  Note that the compare method can, and in
  236.  * most cases should, use the set valueMethod, if any were set.
  237.  */
  238. {
  239.     compareMethod = method;
  240.     [self _updateChain];
  241.     
  242.     return self;
  243. }
  244.  
  245. - (SEL)comparisonMethod
  246. {
  247.     return compareMethod;
  248. }
  249.  
  250. - useValueMethod:(SEL)method
  251. /* sets method used to get value for sort key from objects. */
  252. {
  253.     valueMethod = method;
  254.     return self;
  255. }
  256.  
  257. - (SEL)valueMethod
  258. {
  259.     return valueMethod;
  260. }
  261.  
  262. - sort
  263. /* the chain goes something like this: delegate:sortMethod, self:sortMethod,
  264.  * self:shellsort (default).
  265.  */
  266. {
  267.     if (!delegate) {
  268.       if ([self respondsTo:sortMethod])
  269.         [self perform:sortMethod with:self];
  270.     else    [self shellsort];
  271.     }
  272.     else {
  273.       if ([delegate respondsTo:sortMethod])
  274.         [delegate perform:sortMethod with:self];
  275.     else if ([self respondsTo:sortMethod]) {
  276.         [self perform:sortMethod with:self];
  277.     }
  278.     else    [self shellsort];
  279.     }
  280.     sorted = YES;
  281.     return self;
  282. }
  283.  
  284. - insertObject:anObject
  285. /* Inserts object into list in sorted order. if the list is not sorted, the
  286.  * list sorts itself regardless of whether autosort is enabled.
  287.  */
  288. {
  289.     int    index1 = 0, index2 = numElements - 1, mid, val;
  290.     
  291.     if (!sorted)
  292.     [self sort];
  293.     if (anObject == nil)
  294.     return nil;
  295.     mid = (index2 + index1)/2;
  296.  
  297.     if ([self count] == 0) {
  298.     [self insertObject:anObject at:0];
  299.     return self;
  300.     }
  301.     
  302.     while (mid > index1) {
  303.     if (anObject == dataPtr[mid])
  304.         return self;
  305.     if ((val = (int)[compObject perform:compMethod with:anObject
  306.              with:dataPtr[mid]]) < 0) {
  307.         index2 = mid;
  308.     } else if (val == 0) {
  309.         [self insertObject:anObject at:mid + 1];
  310.         return self;
  311.     } else {
  312.         index1 = mid;
  313.     }
  314.       mid = (index2 + index1)/2;
  315.     } if ((val = (int)[compObject perform:compMethod with:anObject
  316.          with:dataPtr[index1]]) < 0) {
  317.     [self insertObject:anObject at:index1];
  318.     } else if ((val = (int)[compObject perform:compMethod with:anObject
  319.               with:dataPtr[index2]]) > 0) {
  320.     [self insertObject:anObject at:index2 + 1];
  321.     } else {
  322.     [self insertObject:anObject at:index1 + 1];
  323.     }
  324.     sorted = YES;
  325.     return self;
  326. }
  327.  
  328. - mergeList:otherList
  329. /* merges otherList into the list, the new list is sorted. */
  330. {
  331.     int i, j, val, ocount;
  332.     BOOL otherSorted, isSortList;
  333.     
  334.     if (![otherList isKindOf:[List class]]) {
  335.     return nil;
  336.     }
  337.     if ([otherList respondsTo:@selector(isSorted)] &&
  338.       [otherList respondsTo:@selector(sort)]) {
  339.     isSortList = YES;
  340.       otherSorted = [otherList isSorted];
  341.     }
  342.     else {
  343.       otherSorted = NO;
  344.     isSortList = NO;
  345.     }
  346.     
  347.     ocount = [otherList count];
  348.     i = j = 0;
  349.     if (!otherSorted && sorted) {
  350.     for (i = 0; i < ocount; i++) {
  351.         [self insertObject:[otherList objectAt:i]];
  352.     }
  353.     }
  354.     else if (otherSorted && sorted) {
  355.     while (j < ocount) {
  356.         while ((val = (int)[compObject perform:compMethod
  357.                 with:dataPtr[i]
  358.                 with:[otherList objectAt:j]]) < 0) {
  359.         i++;
  360.         if (i >= numElements) {
  361.             i = numElements - 1;
  362.         }
  363.         }
  364.         [self insertObject:[otherList objectAt:j] at:i];
  365.         j++;
  366.       }
  367.     }
  368.     else if (!otherSorted && !sorted) {
  369.     [self appendList:otherList];
  370.     [self sort];
  371.     }
  372.     
  373.     return self;
  374. }
  375.  
  376. - (unsigned int)indexOfObjectWithKey:proxy
  377. {
  378.     int    index1 = 0, index2 = numElements - 1, mid, mark, val;
  379.     
  380.     if (proxy == nil || [self count] == 0)
  381.     return NX_NOT_IN_LIST;
  382.  
  383.     if (sorted == NO) {
  384.     [self sort];
  385.     }
  386. //    return [super indexOf:anObject];
  387.     
  388.     mid = (index2 + index1)/2;
  389.     
  390.     while (mid > index1) {
  391.     if ((val = (int)[compObject perform:compMethod with:proxy
  392.              with:dataPtr[mid]]) < 0) {
  393.         index2 = mid;
  394.     }
  395.     else if (val == 0) {
  396.         mark = mid;
  397.         while (val == 0) {
  398.         mark--;
  399.         val = (int)[compObject perform:compMethod with:proxy
  400.             with:dataPtr[mark]];
  401.         }
  402.         return mark + 1;
  403.     }
  404.     else {
  405.         index1 = mid;
  406.     }
  407.       mid = (index2 + index1)/2;
  408.     }
  409.     if (((int)[compObject perform:compMethod with:proxy
  410.         with:dataPtr[index1]]) == 0) {
  411.       return index1;
  412.     }
  413.     if (((int)[compObject perform:compMethod with:proxy
  414.         with:dataPtr[index2]]) == 0) {
  415.     return index2;
  416.     }
  417.     return NX_NOT_IN_LIST;
  418. }
  419.  
  420.  
  421. /*
  422.  * This code was extracted from the /NextDeveloper/Examples/SortingInAction program.
  423.  * The original author's comment:
  424.  *
  425.  *    Because Shellsort is a variation on Insertion Sort, it has the same 
  426.  *    inconsistency that I noted in the InsertionSort class.  Notice where I 
  427.  *    subtract a move to compensate for calling a swap for visual purposes.
  428.  *
  429.  *    Author: Julie Zelenski, NeXT Developer Support
  430.  *    You may freely copy, distribute and reuse the code in this example.  
  431.  *    NeXT disclaims any warranty of any kind, expressed or implied, as to 
  432.  *    its fitness for any particular use.
  433.  *
  434.  * [This sounds like there is unnecessary work happening in this routine, but I
  435.  * didn't dig into it enough to figure out what to change - rjp]
  436.  *
  437.  * Depending on what methods are set (and whether a delegate is set), the
  438.  * comparison method will vary.  The chain of precedence is:
  439.  *    delegate:comparisonMethod, delegate:compare::, self:comparisonMethod,
  440.  *    self:compare::.
  441.  */    
  442. - shellsort
  443. {
  444.     int c, d, stride;
  445.     BOOL found;
  446.     
  447.     stride = 1;
  448.     while (stride <= numElements)
  449.     stride = stride * STRIDE_FACTOR + 1;
  450.     
  451.     while (stride > STRIDE_FACTOR - 1 ) {
  452.     /* loop to sort for each value of stride */
  453.     stride = stride / STRIDE_FACTOR;
  454.     
  455.     for (c = stride; c < numElements; c++) {
  456.         found = NO;
  457.         d = c - stride; 
  458.         
  459.         while ( d >= 0 && !found ) {
  460.         /* move to left until correct place */
  461.         int target = d + stride ;
  462.         
  463.         if ((int)[compObject perform:compMethod
  464.               with:dataPtr[target]
  465.               with:dataPtr[d]] < 0) {
  466.             id tmp = dataPtr[target];     /* swap the elements */
  467.             dataPtr[target] = dataPtr[d];
  468.             dataPtr[d] = tmp ;
  469.             d -= stride;        /* jump by stride factor */
  470.         } else
  471.             found = YES;
  472.         }
  473.     }
  474.     }
  475.     return self;
  476. }
  477.  
  478. - (int)compare:object1 :object2
  479. {
  480.     if ([object1 respondsTo:valueMethod] &&
  481.         [object2 respondsTo:valueMethod]) {
  482.         return [object1 perform:valueMethod] - 
  483.         [object2 perform:valueMethod];
  484.     }
  485.     else
  486.       return ((int)object1) - ((int)object2);
  487. }
  488.  
  489. @end
  490.  
  491. @implementation SortingListDelegate
  492. /*
  493.  * Dummy delegated method
  494.  */
  495. - (int)compare:object1 :object2
  496. {
  497.     return 0;
  498. }
  499.  
  500. - sort:aList
  501. {
  502.     [aList shellsort];
  503.     return self;
  504. }
  505. @end
  506.  
  507.